Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

681.3*D3 --- 681.3*D3 Programming languages --- Programming languages

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

681.3*D3 --- 681.3*D3 Programming languages --- Programming languages

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Programming --- Computer software --- Testing --- -681.3*D3 --- Software, Computer --- Computer systems --- Programming languages --- 681.3*D3 Programming languages --- 681.3*D3 --- Computer software - Testing.

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Programming --- Prolog (Computer program language) --- PROLOG (Langage de programmation) --- 681.3*D3 --- Programming languages --- 681.3*D3 Programming languages

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Constraint Programming (CP) is een hoog-niveau declaratief programmeerparadigma waarbij problemen gemodelleerd worden door middel van constraints (beperkingen) op de probleemvariabelen waaraan alle oplossingen moeten voldoen. Vele problemen van hoge praktische relevantie kunnen eenvoudig beschreven worden via constraints. Zo zijn er toepassingen te vinden in onder andere productieplanning en het opstellen van dienstroosters voor personeel. Een constraint programming systeem omvat een constraint solver. Deze heeft als taak waarderingen voor de probleemvariabelen te vinden die aan alle constraints voldoen. Constraint Programming systemen worden traditioneel opgedeeld op basis van het domein van de variabelen en het type van de ondersteunde constraints. Vele praktische problemen zijn echter moeilijk te modelleren in termen van de standaard constraintdomeinen. Daarom zijn er langs de ene kant systemen ontwikkeld voor meer gespecialiseerde domeinen. Langs de andere kant zijn er faciliteiten ontwikkeld die het eenvoudiger maken om gespecialiseerde constraint solvers te implementeren. Voorbeelden daarvan zijn geattribueerde variabelen en Constraint Handling Rules. Constraint Handling Rules (CHR) is een regelgebaseerde taal, ontworpen voor de implementatie van gespecialiseerde constraint solvers. CHR is een zeer flexibele taal voor de specificatie van de logica van een constraint solver. Flexibele uitvoeringscontrole ontbreekt echter bijna volledig. Uitvoeringscontrole is van fundamenteel belang voor de efficiëntie van CP systemen. Tot dusver is hier echter binnen de context van CHR nauwelijks aandacht aan besteed. In dit proefschrift presenteren we een oplossing voor het probleem van uitvoeringscontrole in CHR. In het bijzonder breiden we CHR uit met hoog-niveau faciliteiten om de specificatie van uitvoeringsstrategieëen te ondersteunen. Meer specifiek breiden we CHR uit met gebruikersgedefinieerde regelprioriteiten, tot CHR-rp. CHR regels komen overeen met constraint propagatoren, en regelprioriteiten maken dus de specificatie van propagatiestrategieën mogelijk. Een geoptimaliseerde implementatie van CHR-rp wordt voorgesteld en empirisch geëvalueerd. Vervolgens breiden we CHR uit met faciliteiten voor de controle van de zoekstrategie. Onze aanpak combineert CHR-or (CHR met disjunctie) en CHR-rp tot een nieuwe taal, CHR-or-brp genaamd, waarin de propagatiestrategie bepaald is d.m.v. regelprioriteiten, en de zoekstrategie d.m.v. vertakkingsprioriteiten. We stellen een raamwerk voor de analyse van de tijdscomplexiteit van CHR-rp programma's voor, door het Logical Algorithms raamwerk (LA) van Ganzinger en McAllester te combineren met CHR-rp. We presenteren vertalingsschema's van en naar LA en stellen een alternatieve implementatie voor CHR-rp voor, die sterke complexiteitsgaranties biedt. Tenslotte onderzoeken we het join order optimalisatieprobleem, hetgeen een belangrijk deel is van geoptimaliseerde CHR compilatie. We presenteren een kostenmodel voor het matchen met meerhoofdige regels, evenals benaderingen voor zijn parameters en methodes om een optimale join order te vinden. Een uitbreiding van het kostenmodel voor CHR-rp wordt gegeven. Constraint Programming (CP) is a high-level declarative programming paradigm in which problems are modeled by means of constraints on the problem variables that need to hold in all solutions to the problem. Many problems of high practical relevance can easily be described in terms of constraints. Example application areas include production planning and crew scheduling. A constraint programming system contains a constraint solver whose task it is to find valuations for the problem variables that satisfy all constraints. Constraint programming systems can be classified by the variable domains and types of constraints their solver supports. However, for many problems it is not so straightforward to create a model in terms of basic constraint domains. Therefore, on the one hand, systems emerged that can handle more specialized constraint domains. On the other hand, facilities were designed that make it easier to implement an application-specific constraint solver. Some notable examples of these facilities are attributed variables, and Constraint Handling Rules. Constraint Handling Rules (CHR) is a rule-based language, designed for the implementation of application-specific constraint solvers. CHR is a very flexible language for the specification of a constraint solvers' logic, but flexible execution control is almost completely lacking. Execution control is of great importance for the efficiency of CP systems. However, so far, the problem of execution control has received only very limited attention in the context of CHR. In this thesis, we propose a solution to the problem of execution control in CHR. In particular, we extend CHR with high-level facilities to support the specification of execution strategies. More precisely, we extend CHR with user-defined rule priorities into CHR-rp. CHR rules correspond to constraint propagators, and so rule priorities enable the specification of propagation strategies. An optimized implementation of CHR-rp is presented and evaluated empirically. Next, we extend CHR with facilities for search strategy control. Our approach combines CHR-or (CHR with disjunction) and CHR-rp into a new language called CHR-or-brp in which the propagation strategy is determined by means of rule priorities, and the search strategy by means of branch priorities. We propose a framework for analyzing the time complexity of CHR-rp programs, by combining the Logical Algorithms framework (LA) of Ganzinger and McAllester with CHR-rp. We present translation schemas from and to LA and propose an alternative implementation for CHR-rp with strong complexity guarantees. Finally, we investigate the join order optimization problem, which is an important aspect of optimized CHR compilation. We propose a cost model for matching multi-headed rules, approximations of its parameters, and methods to find an optimal join order. An extension of the model for CHR-rp is given. Constraint Programming (CP) is een manier van programmeren waarbij problemen beschreven worden door middel van constraints (beperkingen) waaraan alle oplossingen moeten voldoen. Vele problemen van hoge praktische relevantie kunnen eenvoudig beschreven worden via constraints. Bijvoorbeeld, bij het opstellen van dienstroosters voor personeel, zijn mogelijke constraints dat bepaalde werknemers niet op bepaalde dagen kunnen komen werken, of dat er een minimum tijdspanne tussen twee opeenvolgende shiften moet zijn. Constraint Programming systemen ondersteunen slechts bepaalde types van constraints. Vele praktische problemen zijn echter moeilijk uit te drukken in termen van constraints die een gegeven systeem aanbiedt. Daarom zijn er faciliteiten ontwikkeld die het eenvoudiger maken om een constraint programming systeem voor een applicatie-specifieke constraint te ontwikkelen. Een belangrijk voorbeeld van zulke faciliteiten is de programmeertaal Constraint Handling Rules. Constraint Handling Rules (CHR) is speciaal ontworpen voor de implementatie van applicatie-specifieke CP systemen. CHR is gebaseerd op regels die de betekenis van constraints voorstellen in termen van eenvoudigere constraints. Deze regels geven de programmeur een grote flexibiliteit om de semantiek van constraints uit te drukken. De programmeur heeft echter geen controle over wanneer welke regel uitgevoerd wordt. Zulke controle wordt uitvoeringscontrole genoemd, en is van fundamenteel belang voor de efficiëntie van CP systemen. Tot dusver is hier echter binnen de context van CHR nauwelijks aandacht aan besteed. In dit proefschrift presenteren we een oplossing voor het probleem van uitvoeringscontrole in CHR. In het bijzonder breiden we CHR uit met hoog-niveau faciliteiten om de specificatie van uitvoeringsstrategieëen te ondersteunen. Constraint Programming (CP) is a way of programming in which problems are described by means of constraints the solutions need to satisfy. Many problems of high practical relevance can easily be expressed in terms of constraints. For example, in crew scheduling, constraints may include that certain employees cannot come to work on certain days, or that there should be a minimal amount of time between two consecutive work shifts. Constraint programming systems only support certain types of constraints. However, many problems are not easily expressed in terms of the constraints supported by a given system. Therefore, facilities were designed to make it easier to develop a constraint programming system for some application-specific constraint domain. One notable example of these is the programming language Constraint Handling Rules. Constraint Handling Rules (CHR) is specifically designed for the implementation of application-specific CP systems. CHR is based on rules that represent the meaning of a constraint in terms of more simple constraints. These rules give the programmer great flexibility to express the semantics of constraints, but the programmer has no control over which rule is applied when. Such control is called execution control, and is of great importance for the efficiency of CP systems. However, so far, the problem of execution control has received only very limited attention in the context of CHR. In this thesis, we propose a solution to the problem of execution control in CHR. In particular, we extend CHR with high-level facilities to support the specification of execution strategies.

Academic collection --- 681.3*D3 <043> --- Programming languages--Dissertaties --- Theses --- 681.3*D3 <043> Programming languages--Dissertaties